1. Field of the Invention
The present invention generally relates to proximity search techniques, and more specifically, to a method and a system for performing searches based on proximity to a reference location.
2. Description of the Related Art
A geographic location may be represented as latitude and longitude. FIG. 1 illustrates a map of the world with latitude lines shown every 30 degrees and longitude lines shown every 30 degrees. The distance between any two points on the map shown in FIG. 1 may be calculated based on their latitude and longitude positions, and the known radius of the earth (6371.01 km or 3958.76 miles).
There are many ways of obtaining the latitude and longitude for a particular geographic location. Latitude and longitude positions for locations specified using zip codes, postal codes and cities may be obtained from third party databases using a simple table look-up. Also, a handheld electronic device, such as a pocket PC, cell phone or a personal digital assistant (PDA), may have a GPS receiver and associated software for determining the latitude and longitude position of the handheld electronic device.
In the current art, a proximity search of database records with respect to a reference location is carried out by calculating the distances between the reference location and the locations associated with each of the database records. First, the latitude and longitude positions of the reference location are obtained. Second, the latitude and longitude positions of the locations associated with the database records are obtained. Third, the distances between the reference location and the locations associated with the database records are calculated. Fourth, the database records associated with locations that are within a certain distance (as specified in the proximity search request) from the reference location are selected to be included in the search results.
When the number of database records is large, the proximity search method carried out in the above manner becomes computationally very expensive because of the large number of distance calculations that are required. Distance calculations that are based on zip codes and postal codes have been used to reduce the computational cost, but are not very accurate, and only work for locations in countries having postal codes that are mapped to latitude-longitude values. Quad trees and R-Trees that rely on a two-dimensional grid of regions and subregions have been used to describe the locations of objects in a two-dimensional space, but they require binary-like searches to zero in on the appropriate regions. For proximity searching, they are either too inaccurate (e.g., when the region size is large) or computationally too expensive (e.g., when the region size is sufficiently small).